package 力扣.排序.合并排序;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 考点一：逆序对
 * 考点二：索引数组：原实数组不变，变的是索引数组
 */
public class 计算右侧小于当前元素的个数315 {
    int[] ans;
    int[] idx;//索引数组
    public List<Integer> countSmaller(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<>();
        }
        int N = nums.length;
        int[] t = new int[N];//拷贝数组
        ans = new int[N];

        idx = new int[N];
        for (int i = 0; i < N; i++) {
            idx[i] = i;//记录当前操作数的原实下标位置 ，以后我们就操作索引即可
        }
        mSort(nums,0,N,t);
        return Arrays.stream(ans).boxed().collect(Collectors.toList());
    }

    private void mSort(int[] nums, int b, int e, int[] t) {
        if (b >= e || b + 1 >= e){
            return;
        }
        int mid = (b + ((e - b) >> 1));
        mSort(nums, b, mid, t);
        mSort(nums, mid, e, t);

        int i = b,j = mid,to = b;
        while (i < mid || j < e){
            if (j >= e || (i < mid && nums[idx[i]] <= nums[idx[j]])){
                ans[idx[i]] += (j - mid);
                t[to++] = idx[i++];
            }else{
                t[to++] = idx[j++];
            }
        }
        for (int k = b; k < e; k++) {
            idx[k] = t[k];
        }
    }


    public List<Integer> countSmaller2(int[] nums) {
          if (nums == null || nums.length == 0){
              return new ArrayList<>();
          }
          final int N = nums.length;
          int[] ans = new int[N];
          int[] ints = new int[N];//索引数组
        for (int i = 0; i < N; i++) {
            ints[i] = i;
        }
        int[] teNums = new int[N];//临时拷贝索引的顺序
          mergeSort(nums,0,N,ans,ints,teNums);
        ArrayList<Integer> ansList = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            ansList.add(ans[i]);
        }
          return ansList;
    }

    private void mergeSort(int[] nums, int b, int e, int[] ans, int[] ints,int[] teNums) {
        if (b + 1 >= e){//一个
            return;
        }
        int m = b +((e - b) >> 1);
        mergeSort(nums, b, m, ans, ints, teNums);
        mergeSort(nums, m, e, ans, ints, teNums);
        int i = b,j = m;
        int pos = b;
        while (i < m ||j < e){
            if (j >= e || i < m && nums[ints[i]] <= nums[ints[j]]){//每次都是索引在改变
                ans[ints[i]] += j - m;
                teNums[pos++] = ints[i++];
            }else {
                teNums[pos++] = ints[j++];
            }
        }
        for (int k = b; k < e; k++) {
            ints[k] = teNums[k];

        }

    }
}
